1. Technical Field
The present invention relates to an object caching method, particularly to a data structure wherein classes of objects are hierarchically arranged in a plurality of levels, the caching of objects in the data structure, and the discarding of cached objects.
2. Prior Art
As the use of the Internet and Intranet has spread, various computer application programs are being executed in a distributed environment. In addition, object oriented techniques are being employed at the design and analysis stage for the development of application systems, and various data are being expressed as objects in the implementation and stored in distributed computers. Furthermore, computers, such as network computers (NCs) or portable PDAS, whose resources, such as main memories and computation capacities, are quite limited, are frequently being employed.
In such an environment, generally, a local terminal accesses to objects stored in a remote computer. However, taking into consideration the capacity of the terminal and the speed of a network, it is apparent that caching objects required by a terminal in the terminal is a good idea for a program that processes many remote objects. The required object, however, should not be cached as an individual object, but should be cached as one unit of objects constituting a network structure that will be accessed later. This reason can be derived from well-known characteristic of object oriented programming; that is, (1) a lot of messages are transmitted to objects during a process, and the objects which received the messages further may send messages to objects associated with themselves; and (2) as a result of repeating the above process, accesses to a lot of objects associated with each other is frequently performed.
Assume that one part of data in a database is employed as an object to be processed. In actual program development, specifically, legacy database systems are employed unchanged in many cases, and data in such a database can not be accessed as objects. Therefore, only data to be processed is converted into objects and they are copied to an accessible area. In this case, not only a single object but also the associated objects are required for the processing.
As described above, the procedure employed to determine which objects are to be cached has a great influence on the performance at the terminal. Some conventional methods for determining the range of objects to be cached will now be described.
In the object serialization in Java (trademark owned by Sun Microsystems), when a specific object is designated, basically, all the objects that can be reached from the object through references are to be serialized. The basic algorithm is as follows. If a reference to an object appears at the first time during the copying, a reference number is added to the object and the copying process is repeated recursively. As a reference to the same object appears, the number that was assigned to the object at the first appearance is transmitted instead of the object itself. In this manner, a network structure comprising objects that can be traced can be completely transmitted.
This method prevents the omission of objects, but predicting and controlling the quantity of data to be transmitted is difficult, and care should be taken when a network structure is transmitted that comprises many coupled objects. Java RMI (Remote Method Invocation) makes the control possible to a degree by using a transient value for the objects. However, since this is statically determined during the programming and can not be dynamically changed in accordance with various execution situations, this method lacks flexibility.
When the contents of a database are substantially converted into objects, a technique is employed where, although it depends on the architecture of the database system, a local pointer and a global pointer are used in the class definition to limit in advance the transfer range of the objects (see Container Object (xe2x80x9cData Model and C++ interface For Object Server Built Like Relational Database,xe2x80x9d Fukuda et. al., 45th Information Processing Meeting (latter half of 1992) (4), p.4-111) and Entity/Dependent (xe2x80x9cSan Francisco Project Technical Summary,xe2x80x9d IBM, http://www.ibm.com/Java/ Sanfrancisco)). However, it is difficult to dynamically change a target to be transferred and a transfer range each time processing is performed.
There is another method that employs a cluster concept to transfer all objects in an associated cluster substantially unchanged (see ObjectStore (xe2x80x9cUser Guide ObjectStore Release 3.0 For OS/2 and AIX/xlc System,xe2x80x9d Object Design Inc., January 1994, pp. 42 to 44)). According to this method, a cluster is specified when an object is instantiated in a secondary storage. Actually, when a hardware page in the secondary storage and in a main memory is employed as a cluster unit, calculations performed by a CPU during the transfer, such as tracing of the object references, are not required, and then more efficient caching is provided. However, since the objects in the cluster are transferred unconditionally, unnecessary objects may be transferred, depending on a method for constructing the cluster. Particularly when much transfer time is required in a distributed environment, the volume of the data communication involved is increased and the performance is deteriorated. In addition, while this method provides control to a degree (it enables selection of a policy for caching) by the cluster unit, it cannot cope with dynamic changes of objects during the execution, especially changes on an object network after the objects are instantiated.
For an application program or a framework, object designers implement a method of caching. If they prepare a program very carefully, this program is quite flexible and provides satisfactory effects. However, this requires a high degree of programming skill, and in particular, it is difficult to maintain the consistency of the reference relationship in the cache when the cached objects are released.
If caching is forcedly released while the above described network structure composed of the objects is being cached, this leads to the illegal release of objects and to the illegal accesses to invalid objects. This occurs because an object can be shared by different network structures, and referencing from one network to another is also possible. Therefore, a special garbage collection procedure for maintaining the consistency is required.
A mechanism for detecting the accesses to objects outside the cache uses hardware or software hooking (see ObjectStore (xe2x80x9cUser Guide Object Store Release 3.0 For OS/2 and AIX/xlc System,xe2x80x9d Object Design Inc., January 1994, pp. 9 to 11). In this system, the cache controller can detect such an access and invoke the cache routine without any extra control code in the application program.
The above described methods for determining the range of objects to be cached can not dynamically change objects to be cached in accordance with the various execution contexts.
Therefore, it is one object of the present invention to provide a method for dynamically changing objects to be cached in accordance with the various execution contexts.
It is another object of the present invention to provide a method for maintaining the consistency among whole cached objects even after the caching strategy changes dynamically.
It is an additional object of the present invention to provide a data structure in which objects to be cached can be dynamically changed.
It is a further object of the present invention to enable the customization of objects to be cached in accordance with the characteristic of an application program.
It is still another object of the present invention to reduce the dynamic calculation costs for determining objects to be cached.
First, an explanation will be given for a data structure which enables to dynamically change objects to be cached. At the least, classes of objects in the data structure is hierarchically arranged in a plurality of levels. Whether an object is cached or not is determined by the level of the class that the object belongs to. In addition, for each level, a class of a root object is defined that is an origin object for calculations to determine objects to be cached when a first object of a first class at a certain level refers to a second object of a second class at another level. Generally, the root object is either an object of a class at the certain level from which the references can be traced to the second object of the second class, or the second object of the second class.
Therefore, the root object may be either the first object of the first class at the certain level, which is a reference source object, or the second object of the second class in said another level, which is a reference destination object. At this time, the process for detecting the root object when determining objects to be cached becomes simple.
According to the depth of the process, a programmer of an application program can define classes hierarchically organized into levels to efficiently cache objects. In addition, this data structure may be defined by a user other than an application programmer because, in the caching process explained below, information inherent to an application program is not employed and caching is performed independently of the logic inherent to the program.
Furthermore, it is possible to define, for each set of the first and second classes, or for the first class, a group comprising classes of objects which can be directly or indirectly traced from the first object of the first class and belong to said another level when the first object of the first class at the certain level refers to the second object of the second class at said another level. In this case, not only the levels, but also the groups of classes, for which a reference between an object of a specific class and an object of another specific class is taken into account, are defined. Therefore, the groups of classes can be used to determine which objects are cached. That is, more detailed caching can be performed based on the reference relationship of objects.
When objects in the data structure in which only levels are defined are cached, following steps are performed: in response to that the first object of the first class at the certain level refers to the second object of the second class at said another level, detecting classes at said another level; and specifying, as objects to be cached, objects that have not yet been cached and that can be traced from the first object of the first class, and that belong to said another level.
A following step may be further included: specifying, as objects to be cached, objects that have not yet been cached and that can be traced from the first object of the first class except objects belonging to said another level and a reference destination object if a reference occurs between levels in an ascending order of levels to be cached. This indicates caching when there is a reference between levels in a descending order of levels to be cached.
When objects in a data structure in which object classes are hierarchically arranged also in groups are cached, following steps are performed: in response to that a third object of a third class at one level refers to a fourth object of a fourth class at another level, calculating a group defined by a set of the third class and the fourth class or the third class; and specifying as an object to be cached, an object of a class that has not yet been cached and that can be traced from the third object of the third class, and that belongs to the group defined by the set of the third class and the fourth class or the third class. As a result, caching consonant with the execution condition can be performed in accordance with the reference from an object of a specific class to an object of another specific class.
Furthermore, a following step may be performed: specifying, as an object to be cached, an object that has not yet been cached and that can be traced from the third object of the third class except objects of classes that belong to the group defined by the set of the third and the fourth classes or the third class and a reference destination object if a reference occurs between levels in an ascending order of levels to be cached. This indicates caching when there is a reference between levels in a descending order of levels to be cached.
The above described caching methods are performed based on the levels of the classes or the groups of the classes. However, the same object is not always cached, even in the same class. Thus, dynamic caching can be performed according to the execution status or the usage condition.
A method for discarding objects in a cache comprises the steps of: detecting a key object for a level n, wherein the key object is an object of a class at the level nxe2x88x921 in the cached order and refers to an object of a class at the level n; invalidating a reference from the detected key object for the level n to the object of the class at the level n; and discarding objects of classes that belongs to the level n and subsequent levels and that can be traced from the key object for the level n. In this case, the objects at the n-th level and the subsequent in the caching order are discarded based on the key object for level n, which is an object of a class at the nxe2x88x921-th level in the caching order and refers to an object of a class at the level n, so that the consistency of the reference relationship can be maintained. This method is initiated upon receipt of an instruction from another program and etc.
The above method can be implemented by a program or by a dedicated apparatus. Such a modification on the implementation is normally performed by one having ordinary skill in the art. It is also performed by one having ordinary skill in the art that the above described program and data structure are stored on a storage medium, such as a CD-ROM or a floppy disk.